#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=14942777
#Google interview question
"""
From the set of natural integer numbers
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}

Write an algorithm to compute the rearrangement of x that is closest to y but still greater than y. Both x and y have the same number of digits.

So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is greater than y = 2410 and closer than any other arrangements of x.

And whats the time complexity of this algorithm?
"""
import os, re, sys, getopt
import logging
import locale

def pick_digit(digits, min_value):
    low, high = 0, len(digits)
    result = -1
    while low < high:
        m = (low + high) / 2
        if digits[m] == min_value: break
        elif digits[m] < min_value: low = m + 1
        else: high = m
    if digits[m] < min_value: m += 1
    if m > len(digits) - 1: return -1
    return m

def rearrange_x(x, y, result, index):
    digit_index = pick_digit(x, y[index])
    if digit_index == -1: return -1
    digit = x[digit_index]
    del x[digit_index]
    result.append(digit)
    if digit > y[index]:
        result += x
        return 0
    if rearrange_x(x, y, result, index + 1) < 0:
        if digit_index == len(x) - 1: return -1
        result.pop()
        x.insert(digit_index, digit)
        digit_index += 1
        digit = x[digit_index]
        del x[digit_index]
        result.append(digit)
        result += x
    return 0

def rearange_x_david(x, y):
    x, y = list(str(x)), list(str(y))
    x.sort()
    result = []
    if rearrange_x(x, y, result, 0) < 0: return -1
    return int("".join(result))

def rearrange_lobatt(x, y):
    """docstring for rearrange"""
    print "x=" + str(x)
    print "y=" + str(y)
    y.sort()
    return rearrange_helper_lobatt(x, y, 0)

def rearrange_helper_lobatt(x, y, index):
    if index >= len(x): return False, x
    for i, v in enumerate(y):
        if v < x[index]: continue
        if v == x[index]:
            new_arr = y[:i]
            if i + 1 < len(y): new_arr.extend(y[i+1:])
            result, arr = rearrange_helper_lobatt(x, new_arr, index + 1)
            if result: return True, arr
            elif i < len(y): continue
        else:
            arr = x[:index] + [v] + y[:i]
            if i < len(y):arr.extend(y[i + 1:])
            return True, arr
    return False, x

if __name__ == '__main__':
    try:
        opts, args = getopt.getopt(sys.argv[1:], 'd:', ['date=', 'debug'])
        for opt, arg in opts:
            if opt in ['-d', '--date']: date = datetime.date(int(arg[:4]), int(arg[4:6]), int(arg[6:8]))
            elif opt in ['--debug']:
                debug = True
    except getopt.GetoptError, err:
        print str(err)
        print __doc__
        sys.exit(1)
    print rearange_x_david(1357, 1395) 
    print "==>begin test lobatt"
    for i in xrange(0, 10):
        #do not support 0 in array for simplicity
        from utils import random_arr
        print rearrange_lobatt(random_arr(5, 1, 9), random_arr(5, 1, 9))
        print "-------------"
